The present invention relates to an apparatus for division of binary coded decimal numbers and more particularly to a binary coded decimal number division apparatus which is capable of realizing optimized decimal number division effected by making reference to a quotient prediction table.
In the division of binary numbers, use is made of a quotient prediction table with a view to attaining a high-speed arithmetic operation as referred to in, for example, the above-referenced application. In the case of the division of binary coded decimal numbers, it is equally possible to adopt a process in which a quotient in binary coded decimal representation is determined on a digit-by-digit basis starting from the most significant or highest-order digit by making use of a quotient prediction table.
FIG. 1 of the accompanying drawings shows in a block diagram a binary coded decimal number division circuit in which a quotient prediction table is incorporated. This subject matter is presented by way of explanation, but is not publicly known nor prior art to this application. Referring to this figure, a dividend placed in a dividend register 1 and a divisor set in a divisor register 3 are applied to the inputs of a decimal addition/subtraction unit 8 together with a selected one of the divisor multiples stored in divisor multiple registers 7. Besides, the significant or higher-order bits of the dividend register 1 and the divisor register 3, respectively, are inputted to a quotient prediction table 4, whereby a predicted quotient is loaded in a quotient prediction register 5. The quotient determined by a quotient decision circuit 11 is loaded in a quotient register 2. The quotient prediction table 4 contains and stores therein predicted quotients each represented by one digit (consisting of four bits) of a binary coded decimal number which is determined by the combination of an input value of the dividend and an input value of the divisor, i.e. the value corresponding to the correct quotient or the value greater than the correct one by "1". It is decided that the value in question corresponds to the correct quotient if a carry is produced in actual subtraction of a multiple of the divisor from the dividend. On the other hand, if no carry is produced, it is determined that the subtraction is excessive. In the latter case, a one-fold multiple of the divisor is subsequently added.
Operation of the binary coded decimal number divide circuit shown in FIG. 1 will be described below in more detail. In precedence to the arithmetic operation, multiples (two-fold to nine-fold multiplies) of a divisor placed in the divisor register 3 are previously loaded in the divisor multiple registers 7, respectively. For determining the quotient of one binary coded decimal digit number on the basis of the value supplied from the dividend register 1 and the value available from the divisor register 3, a predicted quotient of one binary coded decimal digit number (consisting of four bits) is read out from the quotient prediction table 4 in dependence on the address which is prepared on the basis of a predetermined number of more significant bits of the dividend placed in the dividend register 1 and a predetermined number of more significant bits of the divisor placed in the divisor register 3. The predicted quotient thus determined is loaded in the quotient prediction register 5 also referred to as the predicted quotient register. Subsequently, the predicted quotient of four bits thus determined is converted into a selection signal (of three bits) through a predicted quotient conversion circuit 9 for selecting one of multiples contained in the divisor multiple registers 7 to thereby allow a multiple Y of the divisor placed in the register 7 selected by the selection signal to be inputted to the decimal addition/subtraction unit 8, wherein the multiple Y is subtracted from the dividend of value X placed in the dividend register 1. A switching gate 12 selects either one of the output of the divisor register 3 and the output of the divisor multiple register 7 and a switching gate 13 selects either the output of the register 5 or the output of a minus-1 circuit 6 in accordance with the presence or absence of a carry signal CAR outputted from the decimal addition/subtraction unit 10. When a carry signal CAR occurs in the subtraction mentioned above (i.e. "X"-"Y".gtoreq.0), the value outputted from the decimal addition/subtraction unit 8 (that is, the interim remainder) is transferred to the dividend register 1 to be stored therein. The dividend register 1 may thus be referred to as the interim remainder register as well. Simultaneously, with the aid of microprograms the content of the quotient prediction register 5 is transferred intact (i.e. as they are) to the quotient register 2 to be stored therein through the quotient decision circuit 11. After the quotient and the interim remainder have been stored in the register 2 and the register 1, respectively, the dividend register 1 and the quotient register 2 are shifted to the left by one digit of the binary coded decimal number.
On the other hand, when no carry signal occurs in the subtraction mentioned above, that is, the result of the subtraction is negative (i.e. "X"-"Y"&lt;0), the value outputted from the decimal addition/subtraction unit 8 is once transferred to the dividend register 1 to be stored therein, and the value is again inputted to the decimal addition/subtraction unit 8 to be added with the value (one-fold multiple) of the divisor placed in the divisor register 3, the result of the addition being transferred as the interim remainder to the dividend register 1 to be newly stored therein. Simultaneously, a value which corresponds to the content of the quotient prediction register 5 decremented by "1" through the minus-one circuit 6 of the quotient decision circuit 11 is selected and transferred to the quotient register 2 to be stored therein. In this manner, in case of the excessive subtraction, the interim remainder is correctively added to a value in excess of the subtrahend (i.e. one-fold multiple of the divisor) to thereby alter concurrently the quotient digit to the correct value. After the interim remainder and the quotient have been loaded, the dividend register 1 and the quotient register 2 are shifted to the left by one digit or position of the binary coded decimal number. Even when a quotient of 1 is determined for a certain digit, the above non-carry procedures are always taken. Accordingly, in any case, the decimal addition/subtraction unit 8 is controlled to arithmetically operate on the content of the divisor multiple register 7 and the content of the dividend register 1 at first.
In this way, the operations mentioned above are repeated for a required number of times, whereby the quotient represented in the binary coded decimal notation is formed in the quotient register 2 on a digit-by-digit basis starting from the highest-order digit.
FIG. 2 is a diagram illustrating relationships among the four-bit predicted quotients determined by referring to the quotient prediction table 4, the three-bit selection signals produced by the conversion circuit 9 and the divisor multiple registers 7 as well as the multiples stored therein.
As will now be appreciated, in the case of the binary coded decimal number divide apparatus shown in FIG. 1, it is required to provide the predicted quotient conversion or translation circuit 9 for converting the predicted quotient read out from the quotient prediction table 4 into the selection signal for selecting one of the divisor multiple registers 7, because the predicted quotient corresponds to the one decimal number digit (i.e. 4 bits) of the correct quotient or the value greater than it by "1".
Since the quotient prediction table 4 for the binary coded decimal number division has to store therein the correct predicted quotients or values greater by "1", realization of the table 4 by using random access memories (RAMs) each of 4K-bit capacity will require as great a number of RAMs as 1024 in consideration of the absolute quantity of addresses each prepared by three digits of the dividend and two digits of the divisor.
In general, a lot of time is required for reading out data from a RAM as compared with a signal delay time involved by another type of logical circuit. Besides, a RAM of a greater capacity requires a correspondingly longer access time and vice versa. Consequently, when the quotient prediction table 4 is to be realized by using a RAM of a great storage capacity, the access time will be correspondingly increased, while realization of the quotient table by using a number of RAMs each of a small storage capacity connected in series will necessarily result in a correspondingly increased package area, involving a significant time delay in signal transmission. Accordingly, in either case, a great deal of time will elapse from the access to the quotient prediction table 4 before a provisional quotient is read out therefrom.
Needless to say, an additional delay is brought about because the provisional quotient thus read out from the quotient prediction table 4 has to undergo conversion effected by the conversion circuit 9 for selecting one of the divisor multiple registers 7. As a result, the decimal addition/subtraction unit 8 cannot perform a fast operation, thus prolonging the arithmetic operation time.
Furthermore, it must be pointed out in connection with the quotient prediction table 4 that in case the unused address among the successive addresses which is not designated by the combination of the more significant bits of the divisor and the divided, respectively, is merely loaded with "0s", an erroneous access to the unused address due to a fault of the address line would result in the reading-out of "0s", which can not however be discriminated from "0" bits of the predicted quotient. To eliminate this difficulty, fail-safe measures are required, such as, for example, writing of a parity error pattern obtained by inverting a parity bit at all the unused addresses of the quotient prediction table 4 so that a fault on an address line can be detected when the unused address is erroneously accessed.